#include <vector>
#include <iostream>

using namespace std;

bool isValidAtPosition(int value, int row, int col, vector<vector<int>> &board);
bool tryDigitsAtPosition(int row, int col, vector<vector<int>> &board);
bool solve(int row, int col, vector<vector<int>> &board);



bool solve(int row, int col, vector<vector<int>> &board) {
  if (col == board[row].size()) {
    ++row;
    col = 0;

    if (row == board.size()) {
      return true;
    }
  }

  if (board[row][col] == 0) {
    return tryDigitsAtPosition(row, col, board);
  }

  return solve(row, col + 1, board);
}

bool solve1(int row, int col, vector<vector<int>> &board) {
  if (col == board[row].size()) {
    ++row;
    col = 0;

    if (row == board.returnsize()) {
      return true;
    }
  }

  if (board[row][col] == 0) {
    for (int i = 1; i < 10; ++i) {
      vector<vector<int>> copy = board;

      if (isValidAtPosition(i, row, col, board)) {
        copy[row][col] = i;

        if (solve(row, col + 1, copy)) {
          board = copy;
          return true;
        }
      }
    }

    return false;
  }

  return solve(row, col + 1, board);
}

bool tryDigitsAtPosition(int row, int col, vector<vector<int>> &board) {
  for (int i = 1; i < 10; ++i) {
    if (isValidAtPosition(i, row, col, board)) {
      board[row][col] = i;

      if (solve(row, col + 1, board)) {
        return true;
      }
    }
  }

  board[row][col] = 0;
  return false;
}

// Return if we could put `value` at (row, col) of board.
bool isValidAtPosition(int value, int row, int col, vector<vector<int>> &board) {
  if (find(board[row].begin(), board[row].end(), value) != board[row].end()) {
    return false; // The value exists in board
  }

  for (vector<int> v : board) {
    if (v[col] == value) {
      return false;
    }
  }

  int startRow = row / 3 * 3;
  int startCol = col / 3 * 3;

  for (int r = startRow; r < startRow + 3; ++r) {
    for (int c = startCol; c < startCol + 3; ++c) {
      if (board[r][c] == value) {
        return false;
      }
    }
  }

  return true;
}

int main(int argc, char const *argv[])
{
  /* code */
  vector<vector<int>> sudoku {
    {5, 3, 0, 0, 7, 0, 0, 0, 0},
    {6, 0, 0, 1, 9, 5, 0, 0, 0},
    {0, 9, 8, 0, 0, 0, 0, 6, 0},
    {8, 0, 0, 0, 6, 0, 0, 0, 3},
    {4, 0, 0, 8, 0, 3, 0, 0, 1},
    {7, 0, 0, 0, 2, 0, 0, 0, 6},
    {0, 6, 0, 0, 0, 0, 2, 8, 0},
    {0, 0, 0, 4, 1, 9, 0, 0, 5},
    {0, 0, 0, 0, 8, 0, 0, 7, 9}
  };

  vector<vector<int>> sudoku1 {
    {0, 0, 0, 0, 0, 0, 0, 0, 0},
    {0, 0, 0, 0, 0, 0, 0, 0, 0},
    {0, 0, 0, 0, 0, 0, 0, 0, 0},
    {0, 0, 0, 0, 0, 0, 0, 0, 0},
    {0, 0, 0, 0, 0, 0, 0, 0, 0},
    {0, 0, 0, 0, 0, 0, 0, 0, 0},
    {0, 0, 0, 0, 0, 0, 0, 0, 0},
    {0, 0, 0, 0, 0, 0, 0, 0, 0},
    {0, 0, 0, 0, 0, 0, 0, 0, 0}
  };

  solve1(0, 0, sudoku);

  for (auto v : sudoku) {
    for (int n : v) {
      cout << n << " ";
    }

    cout << endl;
  }
  return 0;
}
